package com.algorithm.example;

import org.springframework.stereotype.Component;

/**
 * <p>
 * 二分法
 * </p>
 *
 * @author lzt
 * @version 1.0
 * @since 2024/1/14 21:51
 */
@Component
public class Dichotomy {

    /**
     * 初始二分法
     */

    public int dichotomy(int[] A, int target) {
        int i = 0;
        int j = A.length - 1;

        while (i <= j) {
            int m = (i + j) >>> 1; // >>> 无符号位运算，可以避免数值超过int的最大值
            if (target < A[m]) { // 在左边
                j = m - 1;
            } else if (target > A[m]) { // 在右边
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }


    /**
     * 改动版二分查找
     */

    public int dichotomyPlus(int[] A, int target) {
        int i = 0;
        int j = A.length; // 定义为不参与计算的边界值
        while (i < j) { // j不参与计算
            int m = (i + j) >>> 1;
            if (A[m] < target) { // 在右边
                i = m + 1; //
            } else if (target < A[m]) { // 在左边
                j = m;
            } else {
                return m;
            }
        }
        return -1;
    }

    /**
     * 平衡版二分查找
     */


    public int balanceDichotomy(int[] A, int target) {
        int i = 0;
        int j = A.length;
        while (1 < j - i) {
            int m = (i + j) >>> 1;
            if (target < A[m]) { // 在左边
                j = m;
            } else {            // 在右边
                i = m;
            }
        }
        if (A[i] == target) {
            return i;
        } else {
            return -1;
        }
    }

    /**
     * java版二分查找
     */

    public int javaDichotomy(int[] A, int target) {
        int i = 0;
        int j = A.length - 1;

        while (i <= j) {
            int m = (j + i) >>> 1;
            if (target < A[m]) {
                j = m - 1;
            } else if(target > A[m]) {
                i = m + 1;
            } else {
                return m;
            }
        }
        // 返回未找到的元素应该插入的位置
        return -(i + 1);
    }

    /**
     * 重复元素最左元素二分查找
     */
    public int LeftDichotomy(int[] A, int target) {
        int i = 0;
        int j = A.length - 1;
        while (i <= j) {
            int m = (j + i) >>> 1;
            if (target <= A[m]) {
                j = m - 1;
            } else if(target > A[m]) {
                i = m + 1;
            }
        }
        // 返回重复元素最左元素
        return i;
    }


    /**
     * 重复元素最右元素二分查找
     */
    public int RightDichotomy(int[] A, int target) {
        int i = 0;
        int j = A.length - 1;
        while (i <= j) {
            int m = (j + i) >>> 1;
            if (target < A[m]) {
                j = m - 1;
            } else {
                i = m + 1;
            }
        }
        // 返回重复元素最右元素
        return i - 1;
    }
}
